import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] arr = new int[]{1,8,1,8,2,1,2,8,5,2,0};
        s.shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public void shellSort(int[] arr) {
        /**
         * 希尔排序（直接插入排序 + 预排序 + 缩小增量法优化）*/
        int len = arr.length / 2;
        while(len >= 1) {
            shell(arr, len);
            len /= 2;
        }
    }

    private void shell(int[] arr, int gap) {
        /**
         * 对不同增量进行排序*/
        for(int i = gap; i < arr.length && i < gap+gap; i++) { // -固定每组起始下标
            for(int j = i; j < arr.length; j+=gap) { // -枚举单组元素，作直接插入排序
                int k = j - gap;
                int key = arr[j];
                while(k >= 0 && arr[k] > key) {
                    arr[k+gap] = arr[k];
                    k -= gap;
                }
                arr[k+gap] = key;
            }
        }
    }
}
